package com.fw.leetcode;


import com.fw.leetcode.binarysearch.Num_0069;
import com.fw.leetcode.binarysearch.Num_0162;
import com.fw.leetcode.binarysearch.Num_0268;
import com.fw.leetcode.binarysearch.Num_0349;
import com.fw.leetcode.binarysearch.Num_0436;
import com.fw.leetcode.doublepointer.Num_0026;
import com.fw.leetcode.doublepointer.Num_0031;
import com.fw.leetcode.doublepointer.Num_0088;
import com.fw.leetcode.doublepointer.Num_0125;
import com.fw.leetcode.doublepointer.Num_0165;
import com.fw.leetcode.doublepointer.Num_0189;
import com.fw.leetcode.doublepointer.Num_0295;
import com.fw.leetcode.dynamicprogram.Num_0070;
import com.fw.leetcode.dynamicprogram.Num_0118;
import com.fw.leetcode.dynamicprogram.Num_0198;
import com.fw.leetcode.dynamicprogram.Num_0322;
import com.fw.leetcode.greedy.Num_0122;
import com.fw.leetcode.greedy.Num_0409;
import com.fw.leetcode.greedy.Num_0410;
import com.fw.leetcode.greedy.Num_0455;
import com.fw.leetcode.heap.Num_0215;
import com.fw.leetcode.heap.Num_0373;
import com.fw.leetcode.linkedlist.Num_0002;
import com.fw.leetcode.linkedlist.Num_0024;
import com.fw.leetcode.linkedlist.Num_0061;
import com.fw.leetcode.linkedlist.Num_0082;
import com.fw.leetcode.linkedlist.Num_0092;
import com.fw.leetcode.linkedlist.Num_0143;
import com.fw.leetcode.linkedlist.Num_0160;
import com.fw.leetcode.linkedlist.Num_0206;
import com.fw.leetcode.linkedlist.Num_0876;
import com.fw.leetcode.matrix.Num_0048;
import com.fw.leetcode.matrix.Num_0054;
import com.fw.leetcode.matrix.Num_0073;
import com.fw.leetcode.matrix.Num_0289;
import com.fw.leetcode.queue.Num_0387;
import com.fw.leetcode.recursion.Num_0021;
import com.fw.leetcode.recursion.Num_0050;
import com.fw.leetcode.search.Num_0104;
import com.fw.leetcode.slidingwindow.Num_0187;
import com.fw.leetcode.slidingwindow.Num_0219;
import com.fw.leetcode.stack.Num_0020;
import com.fw.leetcode.stack.Num_0094;
import com.fw.leetcode.stack.Num_0316;
import com.fw.leetcode.stack.Num_0321;
import com.fw.leetcode.stack.Num_0402;
import com.fw.leetcode.tree.Num_0100;
import com.fw.leetcode.tree.Num_0103;
import com.fw.leetcode.tree.Num_0124;
import com.fw.leetcode.tree.Num_0230;
import com.fw.leetcode.tree.Num_0236;

import java.util.Arrays;
import java.util.List;

import static com.fw.leetcode.Label.ARRAYS_SORT;
import static com.fw.leetcode.Label.ARRAY_INDEX;
import static com.fw.leetcode.Label.BINARY_SEARCH;
import static com.fw.leetcode.Label.BINARY_SEARCH_TREE;
import static com.fw.leetcode.Label.BINARY_TREE;
import static com.fw.leetcode.Label.BIT_MAP;
import static com.fw.leetcode.Label.BREADTH_FIRST_SEARCH;
import static com.fw.leetcode.Label.BUBBLE_SORT;
import static com.fw.leetcode.Label.CLIMBING;
import static com.fw.leetcode.Label.DEPTH_FIRST_SEARCH;
import static com.fw.leetcode.Label.DIRECTION_VECTOR;
import static com.fw.leetcode.Label.DOUBLE_POINTER;
import static com.fw.leetcode.Label.DYNAMIC_PROGRAMMING;
import static com.fw.leetcode.Label.ENUMERATION;
import static com.fw.leetcode.Label.GREEDY;
import static com.fw.leetcode.Label.HASH_TABLE;
import static com.fw.leetcode.Label.HEAP_SORT;
import static com.fw.leetcode.Label.ITERATION;
import static com.fw.leetcode.Label.LAYER;
import static com.fw.leetcode.Label.LINKED_LIST;
import static com.fw.leetcode.Label.MARK;
import static com.fw.leetcode.Label.MATRIX;
import static com.fw.leetcode.Label.MAX;
import static com.fw.leetcode.Label.QUEUE;
import static com.fw.leetcode.Label.QUICK_SORT;
import static com.fw.leetcode.Label.RECURSION;
import static com.fw.leetcode.Label.SLIDING_WINDOW;
import static com.fw.leetcode.Label.STACK;
import static com.fw.leetcode.Label.SUM;

public enum Index {
    /**
     * --------------------------- 矩阵 -------------------------------------------
     */
    /*
     * 矩阵旋转
     * 最优：方向向量-分层法（避免标记），时O(mn) 空O(1)
     */
    NUM_0048(Num_0048.class, "Rotate Image", MATRIX, LAYER),
    /*
     * 矩阵螺旋
     * 最优：方向向量-分层法（避免标记，不破坏原位数据），时O(mn) 空O(1)
     * 其次：方向向量-访问原位标记法（破坏原位数据），时O(mn) 空O(1)
     * 其次：方向向量-访问标记法（额外标记数组），时O(mn) 空O(mn)
     */
    NUM_0054(Num_0054.class, "Spiral Matrix", MATRIX, DIRECTION_VECTOR, LAYER, MARK),
    /*
     * 矩阵同行同列设0
     * 最优，第0行列标记：时O(mn) 空O(1)
     * 其次：寻找第一个为0的位置行列标记：时O(mn) 空O(1)，慢在第一步寻找上
     */
    NUM_0073(Num_0073.class, "Set Matrix Zeroes", MATRIX, MARK),
    /*
     * 矩阵生死相邻
     * 最优：矩阵 + 原位标记（高位标记，延迟变更）：时O(mn) 空O(1)
     */
    NUM_0289(Num_0289.class, "Game of Life", MATRIX, MARK),
    /**
     * --------------------------- 二分 -------------------------------------------
     */
    /*
     * 最优：二分，时O(log n) 空O(1) => 最大整数下限 floor(sqrt(x)) 即 [max(i^2) <= x] 位置
     */
    NUM_0069(Num_0069.class, "Sqrt(x)", BINARY_SEARCH),
    /*
     * 寻找峰值元素
     * 最优：二分，时O(log n) 空O(1) => 某个峰顶 nums[i-1] < nums[i] > nums[i+1]
     * 其次：求最大值，时O(n) 空O(1)
     */
    NUM_0162(Num_0162.class, "Find Peak Element", BINARY_SEARCH, MAX, CLIMBING),
    /*
     * 最优：求和，时O(n) 空O(1)
     * 其次：位图，时O(n) 空O(n)
     * 其次：冒泡 + 二分，时O(n^2)+O(log n) 空O(1) => 最小 [index != value] 位置
     */
    NUM_0268(Num_0268.class, "Missing Number", BINARY_SEARCH, BUBBLE_SORT, BIT_MAP, SUM),
    /*
     * 最优：排序 + 双指针，时O(mlogm + nlogn)+O(m+n) 空O(logm + logn)
     * 其次：排序 + 二分，时O(mlogm + nlogn)+O(mlog n) 空O(logm + logn)+O(1)
     */
    NUM_0349(Num_0349.class, "Intersection of Two Arrays", ARRAYS_SORT, DOUBLE_POINTER, BINARY_SEARCH),
    /*
     * 最优：索引 + 排序 + 二分，时O(nlog n)+O(nlog n) 空O(n) => 最小 start j ( >= end i ) 位置
     */
    NUM_0436(Num_0436.class, "Find Right Interval", BINARY_SEARCH, ARRAY_INDEX, ARRAYS_SORT),
    /**
     * --------------------------- 贪心 -------------------------------------------
     */
    /*
     * 股票买卖最大利润
     * 最优：爬坡找最大区间（不算贪心）：时O(n) 空O(1)
     * 最优：贪心：时O(n) 空O(1)
     * 最优：动态规划（数组缩减成单变量）：时O(n) 空O(1)
     * 其次：动态规划（数组）：时O(n) 空O(n)
     */
    NUM_0122(Num_0122.class, "Best Time to Buy and Sell Stock II", GREEDY, DYNAMIC_PROGRAMMING, CLIMBING),
    /*
     * 最长回文串
     * 最优：集合标记 偶数奇数字符统计：时O(n) 空O(m)
     */
    NUM_0409(Num_0409.class, "Longest Palindrome", GREEDY, MARK),
    /*
     * 分割数组最大和最小化
     * 1.动态规划（需要先推出公式，确定边界条件）
     * 动态规划（后缀分割）：时O(n^2×m) 空O(nm)，边界条件调试很费时间
     * 动态规划（前缀分割）- 官方：时O(n^2×m) 空O(nm)，边界条件调试很费时间
     */
    NUM_0410(Num_0410.class, "Split Array Largest Sum", DYNAMIC_PROGRAMMING),
    /*
     * 分饼干
     * 最优：贪心 + 排序 + 双指针：时O(nlog n + mlog m) 空O(logm+logn)
     */
    NUM_0455(Num_0455.class, "Assign Cookies", GREEDY, ARRAYS_SORT, DOUBLE_POINTER),
    /**
     * --------------------------- 动态规划 ---------------------------------------
     */
    /*
     * 爬楼梯
     * 最优：动态规划（滚动数组）：时O(n) 空O(1)
     * 其次：动态规划：时O(n) 空O(n)
     */
    NUM_0070(Num_0070.class, "Climbing Stairs", DYNAMIC_PROGRAMMING),
    /*
     * 杨辉三角 => 小心 ArrayList 坑，int[] 数组各个元素已经默认初始化0能直接寻址，ArrayList 需逐个增长
     * 最优：公式（ArrayList不切分）：时O(n^2) 空O(1)
     * 其次：公式（ArrayList+int[]只遍历前半部分）：时O(n^2) 空O(1)
     * 其次：公式（ArrayList只遍历前半部分）：时O(n^2) 空O(1)
     */
    NUM_0118(Num_0118.class, "Pascal's Triangle", DYNAMIC_PROGRAMMING),
    /*
     * 打家劫舍 房间偷钱最大化
     * 最优：动态规划（公式简化，滚动数组）：时O(n) 空O(1)
     * 其次：动态规划（公式简化）：时O(n) 空O(n)
     * 其次：动态规划（滚动数组）：时O(n) 空O(1)
     * 其次：动态规划：时O(n) 空O(n)
     */
    NUM_0198(Num_0198.class, "House Robber", DYNAMIC_PROGRAMMING),
    /*
     * 零钱兑换
     * 最优：动态规划 + 数组迭代：时O(amount*coins) 空O(amount)
     */
    NUM_0322(Num_0322.class, "Coin Change", DYNAMIC_PROGRAMMING),
    /**
     * --------------------------- 链表 ---------------------------------------
     */
    /*
     * 两数相加（逆序排列位数）
     * 最优：相加后再生成 ListNode：时O(max{m,n}) 空O(1)
     */
    NUM_0002(Num_0002.class, "Add Two Numbers", LINKED_LIST),
    /*
     * 两两交换链表节点
     * 最优：一次遍历（cur指针交换一次默认后移一位）：时O(n) 空O(1)
     */
    NUM_0024(Num_0024.class, "Swap Nodes in Pairs", LINKED_LIST),
    /*
     * 旋转链表
     * 最优：求链表长度：时O(n) 空O(1)
     */
    NUM_0061(Num_0061.class, "Rotate List", LINKED_LIST),
    /*
     * 删除顺序链表中存在重复的元素，仅保留原先无重复的元素
     * 最优：建立辅助头节点：时O(n) 空O(1)
     * 其次：未建立辅助头节点（复杂）：时O(n) 空O(1)
     */
    NUM_0082(Num_0082.class, "Remove Duplicates from Sorted List II", LINKED_LIST),
    /*
     * 反转链表
     * 最优：一次遍历：时O(n) 空O(1)
     */
    NUM_0092(Num_0092.class, "Reverse Linked List II", LINKED_LIST),
    /*
     * 重排链表
     * 最优（优化前两个算法）：快慢指针寻中点切割 + 反转链表 + 交叉合并：时O(n) 空O(1)
     * 其次：切割+倒排+交叉合并：时O(n) 空O(1)
     */
    NUM_0143(Num_0143.class, "Reorder List", LINKED_LIST),
    /*
     * 相交链表 => 相交部分共用同一内存节点（即：引用相等处）（不能反转链表，破坏了链表原始结构）
     * 最优：双指针对齐后二次遍历：时O(m+n) 空O(1)
     * 其次：哈希集合找重复值：时O(m+n) 空O(n)
     */
    NUM_0160(Num_0160.class, "Intersection of Two Linked Lists", LINKED_LIST),
    /*
     * 反转链表
     * 最优：新建链表，原头出，新头进：时O(n) 空O(1)
     */
    NUM_0206(Num_0206.class, "Reverse Linked List", LINKED_LIST),
    /*
     * 链表中点
     * 最优：快慢指针：时O(n) 空O(1)
     * 其次：朴素快慢指针做法：时O(n) 空O(1)
     */
    NUM_0876(Num_0876.class, "Middle of the Linked List", LINKED_LIST),
    /**
     * --------------------------- 搜索 --------------------------------------
     */
    /*
     * 二叉树最大深度
     * 最优：深度优先搜索(递归)：时O(n) 空O(log n)
     * 其次：广度优先搜索(队列)：时O(n) 空O(<n) -> 空O() 依队列长度，最坏情况O(n)
     */
    NUM_0104(Num_0104.class, "Maximum Depth of Binary Tree", BINARY_TREE, DEPTH_FIRST_SEARCH, BREADTH_FIRST_SEARCH),
    /**
     * --------------------------- 二叉树 --------------------------------------
     */
    /*
     * 相同的树
     * 最优：深度优先遍历（递归）：时O(n) 空O(log n)
     */
    NUM_0100(Num_0100.class, "Same Tree", BINARY_TREE, DEPTH_FIRST_SEARCH, BREADTH_FIRST_SEARCH),
    /*
     * 二叉树的锯齿形层序遍历（先从左到右，再从右到左，层层遍历）
     * 最优：广度优先遍历 + 双端队列（两头栈）：时O(n) 空O(n)
     */
    NUM_0103(Num_0103.class, "Binary Tree Zigzag Level Order Traversal", BINARY_TREE, BREADTH_FIRST_SEARCH),
    /*
     * 二叉树中最大路径和
     * 递归（归纳策略，难）：时O(N) 空O(N)
     */
    NUM_0124(Num_0124.class, "Binary Tree Maximum Path Sum", BINARY_TREE, DEPTH_FIRST_SEARCH),
    /*
     * 二叉树最近公共祖先
     * 最优：（挖掘隐含条件，难：仅存在一个 p 或 q 时，最近公共祖先是 p 或 q 自身）深度优先遍历（递归）：时O(n) 空O(log n)
     * 其次：（常规）深度优先遍历（递归）：时O(n) 空O(log n)
     */
    NUM_0236(Num_0236.class, "Lowest Common Ancestor of a Binary Tree", BINARY_TREE, DEPTH_FIRST_SEARCH),
    /*
     * 二叉搜索树（排序树）中第k小的元素，计数从1开始
     * 最优：中序遍历(递归，主动停止)：时O(log n) 空O(log n)
     * 最优：中序遍历(栈，主动停止)：时O(<n) 空O(<n)
     */
    NUM_0230(Num_0230.class, "Kth Smallest Element in a BST", BINARY_SEARCH_TREE, DEPTH_FIRST_SEARCH),
    /**
     * --------------------------- 递归 --------------------------------------
     */
    /*
     * 合并两个排序单链表
     * 最优：双指针：时O(n+m) 空O(1)
     * 其次：递归：时O(n+m) 空O(n+m)
     */
    NUM_0021(Num_0021.class, "Merge Two Sorted Lists", LINKED_LIST, RECURSION),
    /*
     * 计算 x 的 n 次 幂：Pow(x, n)
     * 最优：快速幂 + 迭代（巧妙二进制）：时O(log n) 空O(1)
     * 其次：快速幂 + 递归：时O(log n) 空O(log n)
     */
    NUM_0050(Num_0050.class, "Pow(x, n)", RECURSION, ITERATION),
    /**
     * --------------------------- 栈 --------------------------------------
     */
    /*
     * 有效括号
     * 栈：时O(n) 空O(n)
     */
    NUM_0020(Num_0020.class, "Valid Parentheses", STACK),
    /*
     * 二叉树中序遍历
     * 迭代：栈
     * 递归：深度优先遍历
     */
    NUM_0094(Num_0094.class, "Binary Tree Inorder Traversal", STACK, RECURSION),
    /*
     * 去除重复字母（在不打乱字符相对顺序的情况下返回最小字典序）（观察到字符大小的起伏变化）
     * 最优：贪心 + 单调栈（需要寻找规律）：时O(n) 空O(<26)
     */
    NUM_0316(Num_0316.class, "Remove Duplicate Letters", STACK, GREEDY),
    /*
     * 拼接最大数（长度k）（观察到数字大小的起伏变化）
     * 枚举 + 单调栈 + 合并：时O(k(m+n+k^2)) 空O(k) => 枚举后，对左右两个序列分别求最大子序列，后合并求最大值
     */
    NUM_0321(Num_0321.class, "Create Maximum Number", STACK, ENUMERATION),
    /*
     * 移出k位数字（观察到数字大小的起伏变化）
     * 最优：贪心 + 单调栈：时O(n) 空O(n)
     */
    NUM_0402(Num_0402.class, "Remove K Digits", STACK),
    /**
     * --------------------------- 队列 --------------------------------------
     */
    /*
     * 字符串中第一个唯一字符的索引位置
     * 1.哈希表记录频次
     * 2.哈希表+队列更复杂，没必要
     */
    NUM_0387(Num_0387.class, "First Unique Character in a String", QUEUE),
    /**
     * --------------------------- 双指针 --------------------------------------
     */
    /*
     * 删除有序数组中的重复项（原位操作）
     * 双指针：时O(n) 空O(1)
     */
    NUM_0026(Num_0026.class, "Remove Duplicates from Sorted Array", DOUBLE_POINTER),
    /*
     * 下一个全排列（原位更新）
     * [只能靠背] 双指针：时O(n) 空O(1)
     */
    NUM_0031(Num_0031.class, "Next Permutation", DOUBLE_POINTER),
    /*
     * 合并两个数组（nums1原位） nums1+nums2->nums1
     * 最优：逆向双指针：时O(m+n) 空O(1)
     * 其次：正向双指针：时O(m+n) 空O(m+n)
     */
    NUM_0088(Num_0088.class, "Merge Sorted Array", DOUBLE_POINTER),
    /*
     * 验证回文串
     * - 在删除非英文字符后，同时转大写字母为小写字母 [a-zA-Z0-9]，验证是否回文串（不能更改相对位置）
     * 最优：双指针（原位比较）：时O(n) 空O(1)
     */
    NUM_0125(Num_0125.class, "Valid Palindrome", DOUBLE_POINTER),
    /*
     * 比较版本号
     * 分割字符串+单指针：时O(n+m) 空O(<n+m)
     * 双指针（遍历中分割）：时O(n+m) 空O(1)
     */
    NUM_0165(Num_0165.class, "Compare Version Numbers"),
    /*
     * 轮转数组
     * 最优（耗时最短）：分段翻转：时O(n) 空O(1)
     * 其次（耗时其次）：位置映射额外数组：时O(n) 空O(n)
     * 其次（耗时最长）：环形单指针：时O(n) 空O(1)
     */
    NUM_0189(Num_0189.class, "Rotate Array", DOUBLE_POINTER),
    /*
     * 数据流中的中位数（难）
     * 左右优先队列(堆)：时O(log n) 空O(n)
     * --双指针（未实现）
     */
    NUM_0295(Num_0295.class, "Find Median from Data Stream", DOUBLE_POINTER, HEAP_SORT),
    /**
     * ----------------------------- 堆 ---------------------------------------
     */
    /*
     * 数组中第k个最大元素
     * 最优：快速排序变种（递归，难）：时O(n) 空O(log n)
     * 其次：堆排序(非递归)：时O(nlog n) 空O(1)
     */
    NUM_0215(Num_0215.class, "Kth Largest Element in an Array", HEAP_SORT, QUICK_SORT),
    /*
     * 查找和最小的 K 对数字（nums1 | nums2 已顺序排列）
     * 堆（难）：时O(klogk) 空O(k)
     */
    NUM_0373(Num_0373.class, "Find K Pairs with Smallest Sums", HEAP_SORT),
    /**
     * --------------------------- 滑动窗口 --------------------------------------
     */
    /*
     * 存在重复元素 II (k间距内)
     * 哈希集合 + 滑动窗口：时O(n) 空O(k)
     */
    NUM_0219(Num_0219.class, "Contains Duplicate II", SLIDING_WINDOW),
    /*
     * 重复的DNA序列（重复出现的10字母序列）
     * 哈希表 + 滑动窗口(字符位编码)：时O(n) 空O(n)  <= 时间提升不明显
     * 哈希表：时O(nk) 空O(nk)
     */
    NUM_0187(Num_0187.class, "Repeated DNA Sequences", SLIDING_WINDOW, HASH_TABLE);

    private final Class<? extends LeetCode> leetCode;
    private final String title;
    private final List<Label> labels;

    Index(Class<? extends LeetCode> leetCode, String title, Label... labels) {
        this.leetCode = leetCode;
        this.title = title;
        this.labels = Arrays.asList(labels);
    }
}
